home *** CD-ROM | disk | FTP | other *** search
/ Acorn User: China / Acorn User China CD-ROM (UK) (Disc B) / Acorn User China CD-ROM (UK) (Disc B).bin / STUTTGART / DATABASE / ULTIMATE / a252colr.txt < prev    next >
Encoding:
Internet Message Format  |  1993-08-09  |  11.6 KB
  1. From: RWilson@acorn.co.uk
  2. Subject: Dithering in general
  3. Date: 30 Jan 92 12:26:11 GMT
  4.  
  5. As well as the deathless 'How to find the closest colour out of the RISC OS
  6. 256' (yes, *anyone* can use this code (especially Find256) - we'd like an
  7. acknowledgement, please!), here are some notes on dithering:
  8.  
  9. (a) There are some text books that get the Floyd Steinberg error weights WRONG
  10. - the books say 2/8 3/8 and 3/8, but this (although cheaper to calculate)
  11. is not F-S, where the weights are 7/16, 5/16, 3/16 and 1/16.
  12.  
  13. (b) ALL dithering algorithms look 'better' (less prone to regular artifact
  14. patterning) if the display is scanned serpentine (l-r one raster line,
  15. then r-l).
  16.  
  17. (c) There are more expensive (and slightly better than F-S) schemes: see
  18. "Digital Halftoning" by Robert Ulichney published by the MIT Press, ISBN
  19. 0-262-21009-6.
  20.  
  21. (d) ChangeFSI gets right. :-)
  22.  
  23. (e) For god's sake, allow people access to the undithered data.
  24.  
  25. --Roger
  26.  
  27.  
  28. From: RWilson@acorn.co.uk
  29. Subject: How to find the closest colour out of the RISC OS 256
  30. Date: 30 Jan 92 12:20:23 GMT
  31.  
  32. ; MACRO ColErr
  33. ;
  34. ; Calculates an error value in $error corresponding to the difference
  35. ; between the two colours $col1 and $col2.  Requires two temporary
  36. ; registers.  All registers must be different.  This routine requires
  37. ; 16 instructions, three of which are multiples plus for instructions
  38. ; for the error loading calculations.  To speed up the multiplies
  39. ; the error value for each component is made positive.
  40. ;
  41. ; The error calculation is controlled by the following ``loading'' values.
  42. ; The basic component error calculation, given components c1 and c2 from
  43. ; $col1 and $col2, is:-
  44. ;
  45. ;       e := ((c1-c2) ^ 2) * load
  46. ;
  47. ; Thus a higher ``load'' makes errors in the component more significant when
  48. ; the component value itself is small, however has little effect when the
  49. ; component value is large.  Each loading must not exceed 65536/3 or the
  50. ; error calculation may overflow.  If a loading exceeds 32768/3 the result may
  51. ; have the top bit set.  The loadings are determined algorithmically by the
  52. ; following macros - this avoids having to do a real multiplication.  The
  53. ; macros have the form:-
  54. ;
  55. ;       XWeight $err, $sqr
  56. ;
  57. ; and calculate:-
  58. ;
  59. ;       $err = $sqr * XLoad     (for BLoad)
  60. ;       $err += $sqr * XLoad    (for GLoad, RLoad)
  61. ;
  62. ; $sqr may be overwritten.  They are called in the order BLoad, GLoad
  63. ; RLoad, and are only called if the corresponding loading value is not
  64. ; 1.
  65. ;
  66. BLoad   EQU     1
  67.         MACRO
  68. $label  BWeight $error, $sqr
  69.         ASSERT  0
  70.         MEND
  71.  
  72. GLoad   EQU     10
  73.         MACRO
  74. $label  GWeight $error, $sqr
  75. $label  ADD     $sqr, $sqr, $sqr, LSL #2
  76.         ADD     $error, $error, $sqr, LSL #1
  77.         MEND
  78.  
  79. RLoad   EQU     3
  80.         MACRO
  81. $label  RWeight $error, $sqr
  82. $label  ADD     $sqr, $sqr, $sqr, LSL #1
  83.         ADD     $error, $error, $sqr
  84.         MEND
  85.  
  86.         MACRO
  87. $label  ColErr  $error, $col1, $col2, $temp1, $temp2
  88.  
  89. $label  MOV     $temp1, $col1, LSR #24
  90.         SUBS    $temp2, $temp1, $col2, LSR #24
  91.         RSBLT   $temp2, $temp2, #0
  92.    [    BLoad /= 1
  93.         MUL     $temp1, $temp2, $temp2
  94.         BWeight $error, $temp1
  95.    |
  96.         MUL     $error, $temp2, $temp2
  97.    ]
  98.         MOV     $temp2, #255
  99.         AND     $temp1, $temp2, $col1, LSR #16
  100.         AND     $temp2, $temp2, $col2, LSR #16
  101.         SUBS    $temp2, $temp1, $temp2
  102.         RSBLT   $temp2, $temp2, #0
  103.    [    GLoad /= 1
  104.         MUL     $temp1, $temp2, $temp2
  105.         GWeight $error, $temp1
  106.    |
  107.         MLA     $error, $temp2, $temp2, $error
  108.    ]
  109.         MOV     $temp2, #255
  110.         AND     $temp1, $temp2, $col1, LSR #8
  111.         AND     $temp2, $temp2, $col2, LSR #8
  112.         SUBS    $temp2, $temp1, $temp2
  113.         RSBLT   $temp2, $temp2, #0
  114.    [    RLoad /= 1
  115.         MUL     $temp1, $temp2, $temp2
  116.         RWeight $error, $temp1
  117.    |
  118.         MLA     $error, $temp2, $temp2, $error
  119.    ]
  120.         MEND
  121. ;
  122. ; MACRO CompErr
  123. ;
  124. ; This macro also calculates an error value, however the second colour
  125. ; is specified as three separate r, g, b values.  The registers containing
  126. ; these values can be the same, if desired.  The registers should not be
  127. ; the same as any of the other registers.  The calculation needs 16
  128. ; instructions, including three multiplies.
  129. ;
  130.         MACRO
  131. $label  CompErr $error, $col, $red, $green, $blue, $temp1, $temp2
  132.  
  133. $label  SUBS    $temp2, $blue, $col, LSR #24
  134.         RSBLT   $temp2, $temp2, #0
  135.    [    BLoad /= 1
  136.         MUL     $temp1, $temp2, $temp2
  137.         BWeight $error, $temp1
  138.    |
  139.         MUL     $error, $temp2, $temp2
  140.    ]
  141.         AND     $temp1, $col, #&FF0000        ; green component, still shifted
  142.         SUBS    $temp2, $green, $temp1, LSR #16
  143.         RSBLT   $temp2, $temp2, #0             ; |green error|
  144.    [    GLoad /= 1
  145.         MUL     $temp1, $temp2, $temp2
  146.         GWeight $error, $temp1
  147.    |
  148.         MLA     $error, $temp2, $temp2, $error
  149.    ]
  150.         AND     $temp1, $col, #&FF00          ; red component, still shifted
  151.         SUBS    $temp2, $red, $temp1, LSR #8
  152.         RSBLT   $temp2, $temp2, #0             ; |red error|
  153.    [    RLoad /= 1
  154.         MUL     $temp1, $temp2, $temp2
  155.         RWeight $error, $temp1
  156.    |
  157.         MLA     $error, $temp2, $temp2, $error
  158.    ]
  159.         MEND
  160. ;
  161. ; MACRO FindCol
  162. ;
  163. ; This macro finds the closest colour to the given r, g, b triple from
  164. ; an array of (word sized) RGB values (encoded BBGGRR00).  The macro
  165. ; preserves the $red, $green and $blue values, exits with $error set
  166. ; to that of the found colour and $index set to the index of the entry.  Again,
  167. ; all arguments must be different registers.
  168. ;
  169.         MACRO
  170. $label  FindCol $list, $listend, $red, $green, $blue, $error, $index, $ptr, $col, $temp1, $temp2, $temp3
  171.  
  172. $label  MOV     $error, #&FFFFFFFF           ; maximum error
  173.         SUB     $ptr, $list, #4              ; points to entry to last entry tried
  174. 0:      LDR     $col, [$ptr, #4]!
  175.         CompErr $temp3, $col, $red, $green, $blue, $temp1, $temp2
  176.         CMP     $temp3, $error
  177.         MOVLS   $error, $temp3
  178.         SUBLS   $index, $list, $ptr          ; index * 4
  179.         CMP     $ptr, $listend
  180.         BLO     0b
  181.         MOV     $index, $index, LSR #2
  182.         MEND
  183. ;
  184. ; MACRO Find256
  185. ;
  186. ; This macro finds the best matching colour for the *standard* ARM 256 entry palette - the
  187. ; one with the R/G/B/T (tint) bits.  The algorithm returns a palette value encoded in the
  188. ; standard way (BGGRBRTT) in $col and the error in $error.
  189. ; All arguments must be different registers.  The loop is about 44 instructions, including
  190. ; the normal three multiplies.  The code goes round it four times, there is a further 12
  191. ; instruction overhead.
  192. ;
  193. ; The registers must all be different except for $red, $green and $blue, which can be
  194. ; the same if desired.
  195. ;
  196. ; The ARM palette entries are assumed to expand a 4 bit component to an 8 bit component
  197. ; using c<<4|c - this has been determined experimentally to give good results.
  198. ;
  199.         MACRO
  200. $label  Find256 $red, $green, $blue, $error, $col, $tint, $temp1, $temp2, $temp3, $pixel
  201.  
  202. $label  MOV     $error, #&FFFFFFFF
  203.         MOV     $tint, #&30:SHL:23                ; tint bits unexpanded
  204.  
  205. 0:      RSB     $temp1, $tint, #&20:SHL:23        ; overflow is not possible here
  206.         SUB     $temp2, $blue, $blue, LSR #4      ; effectively multiplication by 16/17
  207.         ADDS    $temp1, $temp1, $temp2, LSL #23
  208.         ;
  209.         ; At this point the top bits of $temp1 hold the best blue bit values given
  210.         ; the current $tint tint bits, however the desired value may be >11tt or <00tt,
  211.         ; in either case the top bit (bit 31) of $temp1 will be set, hence the N flag
  212.         ; will be set in the PSR.  We must distinguish overflow (>11tt) from a simple
  213.         ; negative result (<00tt) and truncate both to the appropriate end of the
  214.         ; scale.  We have calculated (blue-tint+&22)<<23.  The overflow (V) flag will
  215.         ; ONLY be set for >11tt; the other possible results (in the range &FF<<23 to
  216.         ; -&17<<23 are representable without overflow), so:-
  217.         ;
  218.         MOVVSS  $temp1, #&7F000000                 ; clears the N flag!
  219.         MOVMI   $temp1, #0
  220.         ;
  221.         ; Now extract the blue bits and reconstruct the real (expanded) blue value.
  222.         ;
  223.         AND     $temp1, $temp1, #&60000000         ; two blue bits
  224.         ADD     $temp1, $temp1, $tint              ; plus tint
  225.         ADD     $pixel, $temp1, $temp1, LSR #4     ; expand component bits - 8 bit blue value
  226.         ;
  227.         ; Calculate the error as above.
  228.         ;
  229.         SUBS    $temp2, $blue, $pixel, LSR #23
  230.         RSBLT   $temp2, $temp2, #0                 ; speeds up multiplication
  231.    [    BLoad /= 1
  232.         MUL     $temp1, $temp2, $temp2
  233.         BWeight $temp3, $temp1
  234.    |
  235.         MUL     $temp3, $temp2, $temp2
  236.    ]
  237.         ;
  238.         ; Repeat this for the green component, accumulating the error
  239.         ;
  240.         RSB     $temp1, $tint, #&20:SHL:23
  241.         SUB     $temp2, $green, $green, LSR #4
  242.         ADDS    $temp1, $temp1, $temp2, LSL #23
  243.         MOVVSS  $temp1, #&7F000000
  244.         MOVMI   $temp1, #0
  245.         ;
  246.         AND     $temp1, $temp1, #&60000000         ; two green bits
  247.         ADD     $temp1, $tint, $temp1              ; 4 bit green value
  248.         ADD     $temp1, $temp1, $temp1, LSR #4     ; expand component bits
  249.         ORR     $pixel, $pixel, $temp1, LSR #8     ; Accumulate bits in $pixel
  250.         ;
  251.         SUBS    $temp2, $green, $temp1, LSR #23
  252.         RSBLT   $temp2, $temp2, #0
  253.    [    GLoad /= 1
  254.         MUL     $temp1, $temp2, $temp2
  255.         GWeight $temp3, $temp1
  256.    |
  257.         MLA     $temp3, $temp2, $temp2, $temp3
  258.    ]
  259.         ;
  260.         ; And the red component:-
  261.         ;
  262.         RSB     $temp1, $tint, #&20:SHL:23
  263.         SUB     $temp2, $red, $red, LSR #4
  264.         ADDS    $temp1, $temp1, $temp2, LSL #23
  265.         MOVVSS  $temp1, #&7F000000
  266.         MOVMI   $temp1, #0
  267.         ;
  268.         AND     $temp1, $temp1, #&60000000         ; two red bits
  269.         ADD     $temp1, $tint, $temp1              ; 4 bit red value
  270.         ADD     $temp1, $temp1, $temp1, LSR #4     ; expand component bits
  271.         ORR     $pixel, $pixel, $temp1, LSR #16    ; Accumulate bits in $pixel
  272.         ;
  273.         SUBS    $temp2, $red, $temp1, LSR #23
  274.         RSBLT   $temp2, $temp2, #0
  275.    [    RLoad /= 1
  276.         MUL     $temp1, $temp2, $temp2
  277.         RWeight $temp3, $temp1
  278.    |
  279.         MLA     $temp3, $temp2, $temp2, $temp3
  280.    ]
  281.         ;
  282.         ; $temp3 contains the error for the ARM value in $pixel (actually this value
  283.         ; is shifted right by 1 bit because of the LSL 23 above).  Check the error
  284.         ; and see if this is a better pixel.
  285.         ;
  286.         CMP     $temp3, $error
  287.         MOVLS   $error, $temp3                ; LS, so selects lower tint in preference
  288.         MOVLS   $col, $pixel                  ; $col holds best match
  289.         ;
  290.         ; Try the next tint
  291.         ;
  292.         SUBS    $tint, $tint, #&10:SHL:23
  293.         BGE     0b
  294.         ;
  295.         ; $error is the error, and is directly comparable with the $error
  296.         ; value from the other macros.  $col to the ARM palette entry using
  297.         ; the appropriate bit manipulations.  The value is currently:-
  298.         ;
  299.         ;       0BBTT011 1GGTT011 1RRTT011 10000000
  300.         ;
  301.         ; We need to convert this to the form:-
  302.         ;
  303.         ;    76543210
  304.         ;    BGGRBRTT
  305.         ;
  306.         AND     $temp1, $col, #&40000000        ; B   (needs >> 23)
  307.         MOV     $temp2, $temp1, LSR #23
  308.         AND     $temp1, $col, #&600000          ; GG  (needs >> 16)
  309.         ORR     $temp2, $temp2, $temp1, LSR #16
  310.         AND     $temp1, $col, #&4000            ; R   (needs >> 10)
  311.         ORR     $temp2, $temp2, $temp1, LSR #10
  312.         AND     $temp1, $col, #&20000000        ; B   (needs >> 26)
  313.         ORR     $temp2, $temp2, $temp1, LSR #26
  314.         AND     $temp1, $col, #&3800            ; RTT (needs >> 11)
  315.         ORR     $col, $temp2, $temp1, LSR #11
  316.         MEND
  317.  
  318.  
  319.